Digital maps are found in a wide variety of devices, including car navigation systems, hand-held GPS units, mobile phones, and also in many websites such as GOOGLE MAPS and MAPQUEST. Although digital maps are easy to use from an end-user's perspective, creating a digital map is a difficult and time-consuming process. Every digital map begins with a set of raw data representing millions of streets and intersections. The raw map data is derived from a variety of sources, each source providing different amounts and types information. In many cases, data from different sources is inaccurate and out of date. Oftentimes the data from the different sources is in a format which is not suitable for use in a real map. Integrating data from these heterogeneous sources so that it can be used and displayed properly is an enormous challenge.
In particular, many sources of map data use a very simple representation of two-way roads. These data sources treat a two-way road as a series of bi-directional road segments. However, in the real world, each two way street may have multiple lanes traveling in opposite directions that can at times be separated by hundreds of feet. In addition, each direction of travel may have its own road attributes, such as addresses, speed restrictions, and the like. Using a single road segment to represent two way roads in digital maps can thus lead to inaccurate maps. For example, if a single bi-directional road segment is overlaid onto a satellite image of a divided highway, the resulting map would be inaccurate because the road segment would be appear to sit on top of the median instead of on the highway itself.